import java.util.ArrayList;
import java.util.List;

/*
    39. 组合总和
    也是选与不选的问题
    重点：如何判断结束条件，因为答案数组的元素个数并不能确定，
    所以在选择这一步中，不将i + 1，可以保证重复选，同时在选择之前判断选择之后是否超过target，减少递归次数
    同时在不选这一步将i + 1，可以保证有结束条件
 */

public class CombinationSum {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        process(candidates,0, target);
        return ans;
    }

    public void process(int[] nums, int i, int target) {
        if (i == nums.length) return;
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }

        process(nums, i + 1, target);
        if (target - nums[i] >= 0) {
            list.add(nums[i]);
            // 重点！
            process(nums, i, target - nums[i]);
            list.remove(list.size() - 1);
        }
    }

}
